package bit_operation;

public class countBits {
    public int[] countBits(int n) {
        int[] ret = new int[n+1];
        for(int i =0;i<=n;i++) {
            ret[i] = countOnes(i);
        }
        return ret;
    }
    public int countOnes(int x) {
        //Brian Kernighan 算法
        int ret = 0;
        while(x > 0) {
            x = x & (x-1);
            ret++;
        }
        return ret;
    }
}
